package iD220711010131;

import java.util.ArrayList;
import java.util.List;

/*
                                                                        k
                                            7                           4
                      /              /   /  |  \   \   \
                     1              2   3   4   5   6   7               3
                     |
                     6
            /    / / /\ \
           1    2 3 4  5 6                                              2
           |
           5
       /  / \ \ \
       1  2 3 4 5                                                       1
       |  
       4
     / |\ \
    1  2 3 4                                                            0
7 3
1 1 5   1 2 4   1 3 3
2 2 3
避免重复的办法：孩子从大于等于父结点的数开始遍历，如上面7和3的例子，呈现递增的形式，就不会重复了



 */

public class MainSubSet2 {
    public static List<List<Integer>> splitNumber(int N, int K) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(N, K, result, new ArrayList<>(), 1);
        return result;
    }

    private static void dfs(int remaining, int k, List<List<Integer>> result, List<Integer> tempList, int start) {
        System.out.println(tempList);
        if (remaining == 0 && k == 0) {
            System.out.println("!");
            result.add(new ArrayList<>(tempList));
            return;
        }
        for (int i = start; i <= remaining && k > 0; i++) {
            tempList.add(i);
            dfs(remaining - i, k - 1, result, tempList, i);
            tempList.remove(tempList.size() - 1);
        }
    }

    public static void main(String[] args) {
        int N = 7;
        int K = 3;
        
        List<List<Integer>> resultList = splitNumber(N, K);
        for (List<Integer> list : resultList) {
            System.out.println(list);
        }
    }
}
